package BackTrack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 全排列 vis[i]
 *
 * 子集用 sI = vis + 不许往回退 （即123 后 无 132x）
 *
 */
public class 全排列46 {
    List<Integer> tmp = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    int[] nums;
    int n;
    boolean[] isVis;
    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        n = nums.length;
        isVis = new boolean[n];
        backTrack();
        return res;
    }
    public void backTrack(){
        if(tmp.size() == n){
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(isVis[i] == true) continue;

            isVis[i] = true;
            tmp.add(nums[i]);
            backTrack();
            isVis[i] = false;
            tmp.remove(tmp.size()-1);
        }
    }
    @Test
    public void test(){
        int[] nums = new int[]{1,2,3};
        System.out.println(permute(nums));
    }
}
